package com.xmh.autocode;


import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class alibabaTest1 {


    @Test
    public void main1() throws Exception {
        count(2, 3, 4);
    }

    // 用来记录深度，就是记录一共有几张牌
    private int CARD_NUMBER;

    // 保存最后一个节点的列表
    private List<Tree> LAST_LIST = new ArrayList<>();


    /*

                px
            /         \
           a           b
        /    \        /    \
       c        d     e    f
     /   \    /   \
    z1   z2  z3   z4   z5 ````````

    主题思路是先建立一个简单的二叉树，然后遍历，给所有节点赋值，然后把所有尾节点（z1 z2 z3。。。）存放好，放到 LAST_LIST里面
    然后便利list，反向查找，获取所有可能性然后得到结果
    这里优化空间很大，而且有很多中做法，我一开始是打算用动态规划的，但是越想越觉得二叉树合适，可能是因为前面有二叉树的题目把·······
    这个算法复杂度为 O(n)····，没办法，没有太多时间，如果给我更多时间我可以有更好的办法·····

     * @param min 第一个数字
     * @param max 第二个数字
     * @param n 多少张牌
     * @return
     */
    private void count(int min, int max, int n) {
        CARD_NUMBER = n;
        //根节点
        Tree root = new Tree();
        root.setParent(null);
        root.setValue(0);
        // 初始化
        setVlue(root, min, max, 0);
        //用于存放结果的集合，去重
        Set<Integer> set = new HashSet<Integer>();

        LAST_LIST.forEach(e -> set.add(count(e)));

        System.out.println(set);
    }

    //末尾节点一直获取父节点，得到改末尾的计算结果
    private int count(Tree tree) {
        return tree.getValue() + (tree.getParent() == null ? 0 : count(tree.getParent()));
    }

    //初始化
    private void setVlue(Tree tree, int min, int max, int depth) {
        if (depth >= CARD_NUMBER) {
            LAST_LIST.add(tree);
            return;
        }

        Tree tree1 = new Tree(tree, min, depth + 1);

        Tree tree2 = new Tree(tree, max, depth + 1);

        tree.setLeft(tree1);

        tree.setRight(tree2);

        setVlue(tree1, min, max, tree1.getDepth());

        setVlue(tree2, min, max, tree2.getDepth());
    }


    class Tree {

        private Tree parent;
        private Tree left;
        private Tree right;
        private int value;
        private int depth;

        public Tree(Tree parent, int value, int depth) {
            this.parent = parent;
            this.value = value;
            this.depth = depth;
        }

        public Tree() {
        }


        public Tree getParent() {
            return parent;
        }

        public void setParent(Tree parent) {
            this.parent = parent;
        }

        public Tree getLeft() {
            return left;
        }

        public void setLeft(Tree left) {
            this.left = left;
        }

        public Tree getRight() {
            return right;
        }

        public void setRight(Tree right) {
            this.right = right;
        }

        public int getValue() {
            return value;
        }

        public void setValue(int value) {
            this.value = value;
        }

        public int getDepth() {
            return depth;
        }

        public void setDepth(int depth) {
            this.depth = depth;
        }
    }


}
